תור עדיפויות (Priority Queue):

• מבנה נתונים אבסטרקטי המאחסן אוסף איברים בעלי מפתח.
• מאפשר לאיברים שונים להכיל מפתח זהה.
• פעולות שהמבנה מממש:
  • פעולת Maximum(S): מחזירה את האיבר בעל המפתח הגדול ביותר.
  • פעולת Insert(S, x): מוסיפה את האיבר x לאוסף S.
  • פעולת ExtractMax(S): מסירה ומחזירה את האיבר עם המפתח הגדול ביותר מ-S.
  • פעולת IncreaseKey(S, x, k): מגדילה את ערך המפתח של x לערך החדש k, בהנחה ש-k גדול או שווה למפתח הנוכחי.

ערימה (Heap):

• ערימה מיוצגת באמצעות עץ בינארי שלם .
• תכונת ערימת מקסימום (Max Heap):
  • כל צומת x מקיים שהמפתח שלו קטן או שווה למפתח ההורה שלו.
• ייצוג במערך:
  • עץ בעל n צמתים מאוחסן במערך A רמה אחר רמה, משמאל לימין.
  • כאשר A.size שומר את מספר האיברים החוקיים בערימה, בעוד ש-A.length הוא הגודל הפיזי המקסימלי של המערך.
  • ניווט במערך:
    • ההורה של תא i ממוקם באינדקס $\lfloor \frac{i-1}{2}\rfloor$ , הילד השמאלי ב-2i+1 והילד הימני ב-2i+2.

פעולות על ערימה:

• פעולת MaxHeapify:
  • פונקציה המקבלת אינדקס i, ומניחה שתתי-העצים של הילדים של הצומת באינדקס כבר מקיימים את תכונת הערימה.
  • הפונקציה בודקת מי הגדול מבין הצומת ושני ילדיו. אם הצומת קטן מאחד מילדיו, היא מחליפה אותו עם הילד בעל המפתח המקסימלי, וקוראת לעצמה ברקורסיה על האינדקס של הילד שהוחלף.
  • זמן ריצה:
    • תלוי בגובה העץ (או תת-העץ), ולכן הסיבוכיות היא $\mathrm{\Theta }(logn)$ או $\mathrm{\Theta }(h)$.
• פעולת BuildMaxHeap:
  • בונה ערימת מקסימום ממערך לא ממוין.
  • הפונקציה רצה בלולאה מאינדקס ההורה של האיבר האחרון $\lfloor \frac{A.size}{2}-1\rfloor$ ויורדת עד לאינדקס 0. על כל צומת כזה היא מפעילה את maxHeapify.
  • זמן ריצה:
    • חסם נאיבי ייתן $\mathrm{\Theta }(n\log n)$ אך ניתוח הדוק מראה שיש לכל היותר $\lceil \frac{n}{2^{h+1}}\rceil$ צמתים בגובה h.
    • סכום זמני הריצה הוא $\sum _{h=0}^{\mathrm{\infty }}\frac{h}{2^h}$, שלפי נוסחת סכום סדרה מתכנס לחסם קבוע של 2. מכאן שזמן הריצה לבניית ערימה הוא $\mathrm{\Theta }(n)$.
• שאר הפעולות (מימוש תור העדיפויות):
  • פעולת Maximum: מחזירה את A בזמן $\mathrm{\Theta }(1)$.
  • פעולת ExtractMax:
    • לוקחת את המקסימום ב-A, מחליפה אותו עם האיבר האחרון במערך, מקטינה את A.size ב-1, ומפעילה MaxHeapify על השורש.
    • זמן ריצה $\mathrm{\Theta }(\log (n))$.
  • פעולת IncreaseKey:
    • מעדכנת את הערך לאינדקס i.
    • לאחר מכן, מבעבעת את האיבר כלפי מעלה בלולאה - כל עוד ערכו גדול מהערך של ההורה שלו, מתבצעת החלפה.
    • זמן ריצה $\mathrm{\Theta }(\log (n))$.
  • פעולת Insert:
    • מוסיפה איבר חדש לסוף המערך עם מפתח התחלתי של מינוס אינסוף, ומגדילה את A.size.
    • לאחר מכן קוראת ל-IncreaseKey כדי לעדכן אותו לערך האמיתי ולבעבע אותו למקום הנכון.
    • זמן ריצה $\mathrm{\Theta }(\log (n))$.

מיון ערימה (Heapsort):

• שלבי האלגוריתם:
  • קורא ל- BuildMaxHeap כדי להפוך את המערך לערימה.
  • לאחר מכן, רץ בלולאה n−1 פעמים: בכל איטרציה שולף את האיבר המקסימלי באמצעות ExtractMax ומציב אותו בסוף המערך המצטמצם.
• זמני ריצה:
  • בניית הערימה לוקחת $\mathrm{\Theta }(n)$
  • כל אחת מ-n−1 הקריאות ל-ExtractMax לוקחת $\mathrm{\Theta }(\log (n))$.
  • הזמן הכולל הוא $\mathrm{\Theta }(n\log (n))$.